/**
* Created with CLion.
* User:Lenovo
* Date:2023-05-31
* Time:1:12
* Description:堆
*/

#include "Heap.h"

void HeapInit(HP *pHp)
{
    assert(pHp);

    pHp -> a = NULL;
    pHp -> size = 0;
    pHp -> capacity = 0;
}

void HeapDestroy(HP *pHp)
{
    free(pHp -> a);
    pHp -> a = NULL;
    pHp -> size = 0;
    pHp -> capacity = 0;
}

void Swap(HPDataType *p1, HPDataType *p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 向上调整算法
void AdjustUp(HPDataType *a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent]) // 小堆
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// 向下调整算法
void AdjustDown(HPDataType *a, int n, int parent)
{
    // 简化运算：假设左孩子就是最小的
    int child = parent * 2 + 1;
    while (child < n) // 临界条件：child 在数组的范围内
        // 为什么是小于号：n 是 size，child 是下标，所以用小于
        // 没有左孩子就一定没有右孩子
    {
        // 选出左右孩子中小/大的那个
        if (child + 1 < n && a[child + 1] < a[child]) // 判断右孩子存在
        {
            child++;// 此时 child 就是小的那个孩子
        }
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(HP *pHp, HPDataType x)
{
    assert(pHp);

    if (pHp -> size == pHp -> capacity)
    {
        int newCapacity = (pHp -> a == NULL ? 4 : 2 * pHp -> capacity);
        HPDataType *tmp = (HPDataType *)realloc(pHp -> a, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL)
        {
            perror("realloc failed");
            return;
        }
        pHp -> a = tmp;
        pHp -> capacity = newCapacity;
    }

    pHp -> a[pHp -> size++] = x;
    // 向上调整
    AdjustUp(pHp -> a, pHp -> size - 1);
}

void HeapPop(HP *pHp) // 删除堆顶的数据
{
    // 1.挪动覆盖，不能保证还是堆 - 父子关系全变了 -> 只能重新建堆
    // 2.首尾元素交换，再删除，再调堆 - 向下调整
    assert(pHp);
    assert(!HeapEmpty(pHp));

    Swap(pHp -> a, pHp -> a + pHp -> size - 1);
    pHp -> size--;
    // 向下调整
    AdjustDown(pHp -> a, pHp -> size, 0);
}

HPDataType HeapTop(HP *pHp)
{
    assert(pHp);
    assert(!HeapEmpty(pHp));

    return pHp -> a[0];
}

bool HeapEmpty(HP *pHp)
{
    assert(pHp);

    return pHp -> size == 0;
}

int HeapSize(HP *pHp)
{
    assert(pHp);

    return pHp -> size;
}


// 弊端：1.先有一个堆，太麻烦  2.空间复杂度 + 拷贝数据
void HeapSort(int *a, int n)
{
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < n; i++)
    {
        HeapPush(&hp, a[i]);
    }

    int i = 0;
    while (!HeapEmpty(&hp))
    {
        int top = HeapTop(&hp);
        a[i++] = top;
        HeapPop(&hp);
    }

    HeapDestroy(&hp);
}

// 改进版 -> 直接建堆，数组看做完全二叉树
void HeapSort2(int *a, int n)
{
    // 建堆：向上调整建堆
    for (int i = 1; i < n; i++) // 从下标为 1 的位置开始插入
    {
        AdjustUp(a, i);
    }

    // 思考：升序排列应该建大堆还是建小堆？
    // 如果建小堆：选出最小的数据放到第 0 个位置之后，(不看第一个)想要继续选出次小的数据的时候，发现只能把剩下的数据看做堆，堆的关系就全乱了，只能重新建堆，代价太大了
    // 如果这样：选出最小的之后，把第一个数据和最后一个交换，忽略掉最后一个，再向下调整，就得到一个新的小堆，再继续调整的话，就得到一个降序排列的数组
    // 因此，反向思考，想要得到升序排列的数组应该建大堆

    int end = n - 1;
    while (end > 0)
    {
        Swap(a, a + end);
        // 再调整，选出次小的数
        AdjustDown(a, end, 0);// end 是最后一个数字的下标，就是前面的数字个数
        end--;
    }
}

// 再优化：向下调整建堆
void HeapSort3(int *a, int n)
{
    // 倒着调整，叶子结点不需要调整 -> 从倒数第一个非叶子节点(最后一个结点的父亲)开始调整
    for (int i = (n - 1 - 1) / 2; i >= 0; i++)
    {
        AdjustDown(a, n, i);// 向下调整建大堆，重复上一个函数的步骤，再继续向下调整
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(a, a + end);
        // 再调整，选出次小的数
        AdjustDown(a, end, 0);// end 是最后一个数字的下标，就是前面的数字个数
        end--;
    }
}

/*
 * 向下调整建堆的时间复杂度：
 * 第 h - 1 层：2 ^ (h - 2) 个结点，需要向下移动 1 层
 * 第 h - 2 层：2 ^ (h - 3) 个结点，需要向下移动 2 层
 * ......
 * 第 2 层：2 ^ 1 个结点，需要向下移动 h - 2 层
 * 第 1 层：2 ^ 0 个结点，需要向下移动 h - 1 层
 * 求和：F(h) = 2 ^ (h - 2) * 1 + 2 ^ (h - 3) * 2 + ... + 2 ^ 1 * (h - 2) + 2 ^ 0 * (h - 1)
 * 等比差数列，应用乘公比错位相减法得到 F(h) = 2 ^ h - 1 - h
 * 假设树的结点 N = 2 ^ h - 1，那么 F(N) = N - log(N + 1)
 *
 * 向上调整建堆的时间复杂度：
 * 第 k 层，有 2 ^ (k - 1) 个结点，需要向上移动 k - 1 次
 * 求和：F(h) = 2 ^ 1 * 1 + 2 ^ 2 * 2 + ... + 2 ^ (h - 1) * (h - 1)
 * 应用乘公比错位相减法，可得 F(h) = (h - 2) * 2 ^ h + 2
 * F(N) = (N + 1) * (log(N + 1) - 2) + 2
 *
 * 总结：
 * 向下调整建堆结点多时移动的次数少，结点少时移动的次数多，向上调整建堆反之
 * 向下调整建堆有着明显优势
 * 建堆的时间复杂度是 O(N)
 *
 * 额外补充：堆排序的时间复杂度
 * 调整：第 k 层有 2 ^ (k - 1) 个结点，每个节点交换到上面，再向下调整需要 k - 1 次
 *      时间复杂度是 2 ^ (k - 1) * (k - 1)
 *      求和，类似于向上调整建堆，时间复杂度是 O(N * logN)
 * 建堆：O(N)
 * 总时间复杂度：O(N * logN + N) = O(N * logN)
 */






